#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back
#define rep(i, x, y) for(int i = (x); i <= (y); i++) 
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int , int >;
using vec = vector < int >;
using veg = vector < pii >;

int read() {
	int x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch == '-', ch = getchar(); 
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return f ? -x : x;
}

const int N = 1e5 + 10;

int n, Q, K;
int f[20][N], g[20][N], a[N], stk[N], top;

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	n = in; K = in; Q = in;
	rep(i, 1, n) a[i] = in;
	rep(i, 1, n) {
		while(top && a[i] >= a[stk[top]]) g[0][stk[top--]] = i;
		g[0][i] = i; stk[++top] = i;
	}
	top = 0;
	per(i, n, 1) {
		while(top && a[i] >= a[stk[top]]) f[0][stk[top--]] = i; 
		f[0][i] = i; stk[++top] = i;
	}
	//	rep(i, 1, n) cerr << f[0][i] << " " << g[0][i] << endl;
	rep(k, 1, 19) rep(i, 1, n)
		f[k][i] = min(f[k - 1][f[k - 1][i]], f[k - 1][g[k - 1][i]]), g[k][i] = max(g[k - 1][g[k - 1][i]], g[k - 1][f[k - 1][i]]);
	while(Q--) {
		int x = in, y = in; if(x > y) swap(x, y);
		int l = x, r = x, ans = 0;
		per(k, 19, 0) {
			int xl = min(f[k][l], f[k][r]), xr = max(g[k][l], g[k][r]);
			if(xr < y) ans += 1 << k, l = xl, r = xr;
		}
		int tmp = r; l = r = y; 
		per(k, 19, 0) {
			int xl = min(f[k][l], f[k][r]), xr = max(g[k][l], g[k][r]);
			if(xl > tmp) ans += 1 << k, l = xl, r = xr;
		}
		printf("%d\n", ans);
	}		
	return 0;
}
